#!/usr/bin/env python3

"""
单链表
"""


class Node:

    def __init__(self, data):
        """
        初始化结点
        """
        self.data = data
        self.next = None

class SingleLinkedList:

    def __init__(self):
        """
        初始化结点
        """
        self.head = Node(None)

    def CreateSingleLinkedList(self):
        """
        创建单链表
        """
        cNode = self.head
        ele = input("请输入当前节点的值: ")
        while ele != '#':
            nNode = Node(int(ele))
            cNode.next = nNode
            cNode = cNode.next
            ele = input("请输入当前节点的值: ")

    def GetLength(self):
        """
        获取单链表长度
        """
        node_len = 0
        cNode = self.head
        while cNode.next != None:
            node_len += 1
            cNode = cNode.next
        #  print("单链表长度为: %d" % node_len)
        return node_len

    def IsEmpty(self):
        """
        判断单链表是否为空
        """
        is_empty = True if self.GetLength() == 0 else False
        #  print("单链表是否为空: {0}".format(is_empty))
        return is_empty

    def InsertElementInTail(self):
        """
        在表中尾端插入某一结点
        时间复杂度: o(n)
        """
        ele = input("请输入链表尾端待插入节点的值: ")
        if ele == '#':
            return
        cNode = self.head
        while cNode.next != None:
            cNode = cNode.next

        nNode = Node(int(ele))
        cNode.next = nNode

    def InsertElement(self):
        """
        在表中任意位置插入某一结点(未完成)
        if index > self.length:
            return 'Error'
        if isinstance(this_node, Node):
            pass
        else:
            this_node = Node(this_node)
        if index == 0:
            this_node.next = self.head
            self.head = this_node
        else:
            p = self.head
            while index-1:
                p = p.next
                index-=1
            this_node.next = p.next
            p.next = this_node
        self.length+=1
        """
        pos = int(input("请输入链表中待插入节点的位置: "))
        ele = input("请输入链表待插入节点的值: ")
        if pos == '' or ele == '#':
            return
        if pos > self.GetLength():
            return

        #  插入新节点
        nNode = Node(int(ele))
        cNode = self.head
        if pos == 0:
            nNode.next = cNode.next
            cNode.next = nNode
        else:
            while pos - 1:
                cNode = cNode.next
                pos -= 1
            nNode.next = cNode.next
            cNode.next = nNode

    def InsertElementInHead(self):
        """
        在表中首端插入某一结点
        时间复杂度: o(1)
        """
        ele = input("请输入链表首端待插入节点的值: ")
        if ele == '#':
            return
        nNode = Node(int(ele))
        cNode = self.head
        nNode.next = cNode.next
        cNode.next = nNode

    def DestorySingleLinkedList(self):
        """
        销毁单链表
        """
        self.head = Node(None)

    def DeleteElement(self):
        """
        删除表中某一结点
        """
        ele = int(input("请输入链表中待删除节点的值: "))
        cNode = self.head
        pNode = self.head
        if self.IsEmpty():
            print("单链表为空")
            return
        while cNode.next != None and cNode.data != ele:
            pNode = cNode
            cNode = cNode.next
        if cNode.data == ele:
            pNode.next = cNode.next
            del cNode
            print("已删除%d结点" % ele)
        else:
            print("未找到%d元素" % ele)

    def GetElement(self):
        """
        获取表中指定位置结点的值
        """
        pos = 0
        dpos = int(input("请输入链表中指定位置: "))
        cNode = self.head
        if self.IsEmpty():
            print("单链表为空")
            return
        if dpos > self.GetLength():
            print("不存在该位置")
            return
        while cNode.next != None:
            pos += 1
            cNode = cNode.next
            if pos == dpos:
                print("{0}位置值为: {1}".format(dpos, cNode.data))
                return cNode.data

    def FindElement(self):
        """
        在表中查找某一结点
        """
        pos = 0
        ele = int(input("请输入链表中待查找节点的值: "))
        cNode = self.head
        if self.IsEmpty():
            print("单链表为空")
            return
        while cNode.next != None and cNode.data != ele:
            cNode = cNode.next
            pos +=1
        if cNode.data == ele:
            print("查找到{0}元素的位置{1}".format(ele, pos))
        else:
            print("未找到%d元素" % ele)

    def VisitElement(self, tNode):
        """
        访问表中某一结点值
        """
        if tNode != None:
            print(tNode.data, "->", end=" ")
        else:
            print("None")

    def TravelElement(self):
        """
        遍历表中所有结点
        """
        print("开始遍历单链表...")
        if self.IsEmpty():
            print("单链表为空")
            return
        cNode = self.head
        while cNode.next:
            cNode = cNode.next
            self.VisitElement(cNode)


if __name__ == "__main__":
    sll_class = SingleLinkedList()
    sll_class.CreateSingleLinkedList()
    #  sll_class.InsertElementInTail()
    #  sll_class.InsertElementInHead()
    sll_class.InsertElement()
    #  sll_class.FindElement()
    #  sll_class.DeleteElement()
    sll_class.TravelElement()
    #  sll_class.DestorySingleLinkedList()
    #  sll_class.TravelElement()
    #  sll_class.GetElement()

